package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Yi Jun jie
 * @Date 2021/3/3 14:21
 * 面试题 04.03. 特定深度节点链表
 */
public class LeetCode0403 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t4.left = t8;
        t2.left = t4;
        t2.right = t5;
        t3.right = t7;
        t1.left = t2;
        t1.right = t3;
        //遍历验证结果
        for (ListNode node : new LeetCode0403().listOfDepth(t1)) {
            while (node != null) {
                System.out.print(node.val + " ");
                node = node.next;
            }
            System.out.println();
        }
    }

    //返回每一层的结点的链表结构(常规的层次遍历)
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode q;//记录出队的结点
        List<ListNode> res = new ArrayList<>();
        ListNode L = new ListNode(0);//初始化一个链表结点
        queue.offer(tree);//入队头结点
        int size;//记录每一层的结点数目
        while (!queue.isEmpty()) {
            size = queue.size();
            ListNode r = L;
            for (int i = 0; i < size; i++) {
                q = queue.poll();//获取出队结点，出队列的就是当前层的结点
                r.next = new ListNode(q.val);//这里采用尾插法插入结点
                r = r.next;//指针往后移动一位
                if(q.left != null) {
                    queue.offer(q.left);
                }
                if(q.right != null) {
                    queue.offer(q.right);
                }
            }
            res.add(L.next);//将每一层的结点信息加入集合中
            L.next = null;//将头结点后面的结点信息置空
        }
        return res.toArray(new ListNode[] {});
    }

    //Definition for a binary tree node.
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    //Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}


